package blueBridge;

/*

product = left * right，(sum/2) * (sum/2)是乘积最大的情况，而且left和right越接近sum/2，乘积就越大
dp[i][j]含义：预期达到j元，目前能凑到的最大金额。此金额作为left，dp[39][sum/2]自然是最接近sum/2的。
        1000        5160        14351       20761       25418    ...     sum/2
5160       0        5160        5160        5160         5160             5160
9191       0        5160        14351       14351       14351            14351
6410       0        
4657       0
7492       0
1531       0
...

 */


public class Main17143 {

    public static void main(String[] args) {
        String str = "5160 9191 6410 4657 7492 1531 8854 1253 4520 9231 1266 4801 3484 4323 5070 1789 2744 5959 9426 4433 4404 5291 2470 8533 7608 2935 8922 5273 8364 8819 7374 8077 5336 8495 5602 6553 3548 5267 9150 3309";
        String[] strNums = str.split(" ");
        int[] nums = new int[40];
        int sum = 0;
        for (int i = 0; i < 40; i++) {
            nums[i] = Integer.parseInt(strNums[i]);
            sum += nums[i];
        }
        int[][] dp = new int[40][sum/2+1];
        for (int i = 1; i < 40; i++) {
            for (int j = 0; j <= sum/2; j++) {
                if (j - nums[i] >= 0) {
                    dp[i][j] = Math.max(dp[i-1][j-nums[i]] + nums[i], dp[i-1][j]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        int left = dp[39][sum/2];
        int right = sum - left;
        System.out.println((long) left * right);
    }

}
